#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

const int N = 1e6 + 10, INF = 0x3f3f3f3f;

int n, m;
int h[N], st = 0, ed = 1, idx = 1;
struct Link {
    int v, l, r;
}arr[N];

int add(int x, int v)
{
    int p = ++idx;
    arr[arr[x].r].l = p;
    arr[p].r = arr[x].r;
    arr[x].r = p; arr[p].l = x;
    arr[p].v = v;
    return p;
}

int pre(int x) { return arr[arr[x].l].v; }
int suf(int x) { return arr[arr[x].r].v; }

struct node
{
    int ls, rs;
    int key, pri;
    int siz;
};


struct FHQTreap1
{
    int root = 0, idx = 0;
    int min_sort_gap = 1e9;
    node tr[N];
    int newnode(int x)
    {
        int p = ++idx;
        tr[p].ls = tr[p].rs = 0;
        tr[p].key = x;tr[p].pri = rand();
        tr[p].siz = 1;
        return p;
    }

    void pushup(int x) { tr[x].siz = tr[tr[x].ls].siz + tr[tr[x].rs].siz + 1; }

    void split(int x, int k, int& l, int& r)
    {
        if (x == 0) { l = r = 0; return; }
        if (tr[x].key <= k) {
            l = x;
            split(tr[x].rs, k, tr[x].rs, r);
        } else {
            r = x;
            split(tr[x].ls, k, l, tr[x].ls);
        }
        pushup(x);
    }

    int merge(int l, int r)
    {
        if (l == 0 || r == 0) return l + r;
        if (tr[l].pri > tr[r].pri) {
            tr[l].rs = merge(tr[l].rs, r);
            pushup(l);
            return l;
        } else {
            tr[r].ls = merge(l, tr[r].ls);
            pushup(r);
            return r;
        }
    }

    int Max(int x)
    {
        while (tr[x].rs) x = tr[x].rs;
        return tr[x].key;
    }

    int Min(int x)
    {
        while (tr[x].ls) x = tr[x].ls;
        return tr[x].key;
    }

    void insert(int x)
    {
        int l, r;split(root, x, l, r);
        if (l != 0) min_sort_gap = min(min_sort_gap, x - Max(l));
        if (r != 0) min_sort_gap = min(min_sort_gap, Min(r) - x);
        root = merge(merge(l, newnode(x)), r);
    }
}a;

struct FHQTreap2
{
    int root = 0, idx = 0;
    node tr[N];
    int newnode(int x)
    {
        int p = ++idx;
        tr[p].ls = tr[p].rs = 0;
        tr[p].key = x;tr[p].pri = rand();
        tr[p].siz = 1;
        return p;
    }

    void pushup(int x) { tr[x].siz = tr[tr[x].ls].siz + tr[tr[x].rs].siz + 1; }

    void split(int x, int k, int& l, int& r)
    {
        if (x == 0) { l = r = 0; return; }
        if (tr[x].key <= k) {
            l = x;
            split(tr[x].rs, k, tr[x].rs, r);
        } else {
            r = x;
            split(tr[x].ls, k, l, tr[x].ls);
        }
        pushup(x);
    }

    int merge(int l, int r)
    {
        if (l == 0 || r == 0) return l + r;
        if (tr[l].pri > tr[r].pri) {
            tr[l].rs = merge(tr[l].rs, r);
            pushup(l);
            return l;
        } else {
            tr[r].ls = merge(l, tr[r].ls);
            pushup(r);
            return r;
        }
    }

    void insert(int x)
    {
        int l, r, p;
        split(root, x, l, r);split(l, x - 1, l, p);
        p = merge(p, newnode(x));
        root = merge(merge(l, p), r);
    }

    void del(int x)
    {
        int l, r, p;
        split(root, x, l, r);split(l, x - 1, l, p);
        p = merge(tr[p].ls, tr[p].rs);
        root = merge(merge(l, p), r);
    }

    int kth(int x, int k)
    {
        if (tr[tr[x].ls].siz + 1 == k) return tr[x].key;
        if (tr[tr[x].ls].siz >= k) return kth(tr[x].ls, k);
        return kth(tr[x].rs, k - tr[tr[x].ls].siz - 1);
    }
}b;

void solve()
{
    arr[st].l = arr[ed].r = -1;
    arr[st].r = ed, arr[ed].l = st;
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;
        h[i] = add(arr[ed].l, x);
        a.insert(x);
        if (i != 1) b.insert(abs(pre(h[i]) - x));
    }

    while (m--) {
        char op[20];cin >> op;
        if (op[0] == 'I') {
            int x, v;cin >> x >> v;
            h[x] = add(h[x], v);
            if (a.min_sort_gap != 0) a.insert(v);
            if (x < n) b.del(abs(suf(h[x]) - pre(h[x])));
            b.insert(abs(pre(h[x]) - v));
            if (x < n) b.insert(abs(suf(h[x]) - v));
        } else if (op[4] == 'G') {
            cout << b.kth(b.root, 1) << '\n';
        } else {
            cout << a.min_sort_gap << '\n';
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
    std::istringstream in(R"()");
    std::cin.rdbuf(in.rdbuf());
#endif
    srand(time(NULL));
    int T = 1;
    //cin>>T;
    for (int i = 1;i <= T;i++) {
        solve();
    }
}